19.5 時間ベースリアルタイムコレクション : Metronome
概要
時間ベーススケジューリング
最低限のミューテータの稼働率をパラメータとし、その稼働率を維持しながらリアルタイム動作するよう設計
Metronome
Java の時間ベースのリアルタイムガベージコレクタ
インクリメンタルマークスイープ方式
必要に応じ部分的な圧縮を行って断片化を避ける
消去バリアを用いた弱い三色不変条件の維持
弱い三色不変条件：黒いオブジェクトが差している白いオブジェクトは灰色保護されている
Brooks の転送ポインタを使用
ミューテータによるアクセスごとに間接参照が必要
ミューテータ利用率
Metronome では実行時間のうち予め決めた割合をミューテータに保証
残り時間をコレクタが自由に使える
時間ウィンドウを10ミリ秒、コレクタのタイムスライス 500マイクロ秒とする
デフォルトのミューテータ利用率は70％
コレクションサイクル中のどの10ミリ秒をとってきても、コレクタが使用するタイムスライスは高々6回
https://gyazo.com/6c3d670c0860a343b15f39997860e514
横軸の時刻が終端の最後10msにおけるミューテータ利用率を表すグラフ
コレクタが忙しいときはこのような使用パターンになることが多い
最初は利用率に余裕があるのでできるだけ使う（A区間）
ある時点で余裕がなくなるので休む（B区間）
余裕が出てきたらまた積極的に使う（C区間）
図19-8 はきっちり70％だけど実際はこんなに精密にはできないことには注意が必要
予測可能性
ここでは以下の2つについて触れる
A: 断片化したヒープに巨大なオブジェクトを割り付けようとして発生する予測不可能性への対処するテクニック
B: コレクタによる停止時間を決定的に短くすることにより予測可能性を向上させるテクニック
アレイレット(Arraylets) (Aについての話題)
配列を複数の固定長のチャンク（アレイレット）に分割して割り付ける
圧縮の必要なしに、ある程度の断片化に対する耐性が得られる
巨大な配列は、連続した1つのデータである背骨（spine）として割り付けられる
背骨には固定長のデータであるアレイレットへのポインタが格納される
配列のデータはアレイレットが持つ
アレイレットのサイズを2べきになっている
間接参照のコスト（添字から要素の位置を特定すること）が配列の添字のシフト演算となり軽量
リードバリア（B について話題かな…）
Brooks のリードバリアを使用
コレクタが移動したかどうかに関係なく一定のオーバーヘッドでオブジェクトにアクセスできる
eager なリードバリア戦略
ヒープから参照をロードするときにその参照を転送
つまり、ロードされた参照が常に to 空間を指すことを保証
スタックやレジスタからのこれらの参照を経由したアクセスには間接参照のオーバーヘッドがかからない
to にいると保証されているのでそもそも間接参照しなくていい（？）
eager にするためのコストは？
オブジェクトを移動させたコレクタのタイムスライス（!= ミューテータのタイムスライス）では常にスタックとレジスタが保持する参照も転送しなければならない
今まではオブジェクトの移動と整合性をとるために考慮すべき参照はすべてヒープの上だった
今回はスタックとレジスタから直接指されている可能性もあるので、そちらの参照も適切に書き換える必要がある
共通部分式の削除によるコスト削減
単に同じ load は何回もやらないようにするというだけだと思う（普通のコンパイラ最適化技法）
バリア沈下によるコスト削減
実際に参照を利用しているところまでバリアを移動させて、バリアと null チェックを同時に行えるようにする最適化
コレクタのスケジューリング
安定したスケジューリングと短時間の割り込まれない停止を両立させるために2つの異なるスレッドを使用
アラームスレッド
非常に高い優先度を持つ（すべてのミューテータより高い）
500マイクロ秒ごとに起動し、コレクタのタイムスライスをスケジュールするかどうかを決める
スケジュールすべきと判断すれば、ミューテータの停止処理を開始し、コレクタスレッドを起動
アラームスレッドが行う処理は10マイクロ秒以下と極めて短く、無視して良い
コレクタスレッド
実際にコレクタの仕事を行うスレッド
アラームスレッドが開始したミューテータスレッドの停止処理を完了させる
残ったタイムスライスでコレクタの仕事をし、ミューテータを起動して再び停止
タイムスライスが終わるまでに仕事を完了できない場合、コレクタはCPUを取り上げられる
ミューテータスレッドの停止
コレクタのタイムスライス中はミューテータは完全に停止している
ミューテータをGCセーフポイントで停止させるのにハンドシェークを用いる
ミューテータはGCセーフポイントで内部的に保持する実行系の全てのメタデータを解放
実行コンテキスト中のすべての参照を決められた場所で保存
GCセーフポイントに到達したことを示すシグナルを出して休止
再開のシグナルが来たら実行コンテキストやメタデータを復帰させて実行を続行
参照を保存し読み直すことによって、参照先がコレクタのタイムスライスの間に移動しても、コレクタが参照を更新できるようになる
eagerなリードバリア戦略のためのコストの部分
コレクタが参照を書き換えるときはヒープ上のオリジナルの参照に加えてここに保存されている参照を書き換える
GCセーフポイントはミューテータが停止するまでの時間の上限が抑えられるようコンパイラによって一定の間隔で挿入される
ミューテータの停止の仕組みは、ミューテータのコードを実行しているスレッドにのみ適用される
ヒープにアクセスしないスレッドやミューテータ以外のネイティブコードを実行するスレッド、停止中のスレッドなどは除外
これらのスレッドはコレクタのタイムスライス中に動いていていいため
これらのスレッドがヒープにアクセスする場合、自分で停止してコレクタのタイムスライスが終わるのを待つ
不揃いなルート走査
コレクタによる参照の転送によってミューテータがオブジェクトへのポインタを見失わないよう、コレクタのタイムスライスごとに各スレッドのスタックを完全に走査
スタック中の参照を適切に書き換えて転送先のオブジェクトを指すようにコレクタが書き換える
このため、アプリケーション開発者はスタックが深くなりすぎないように注意が必要
1つのスレッドのスタック走査は1回のタイムスライスで不可分に行われる必要がある
一方で、スレッドごとに異なるタイムスライスで走査することは許される
複数のミューテータスレッドのそれぞれのスタックの走査は、独立に異なるタイムスライスで走査されうる
コレクタがスレッドのスタック走査中に、ミューテータがインターリーブして実行してよい
複数のスレッドローカルスタックの走査がすべて終わっていなくても、すでに走査が終了したスタックをもつミューテータの実行はインターリーブして実行できるはず
これを実現するため、未走査のスレッドに挿入バリアをかける
コレクタが操作していないルートの参照を、そのスレッドが灰色の境界より後ろに隠さないようにする
解析
Metronomeは、スケジューリングの形式的なモデルを構築したという貢献がある。
定義たち
瞬間割付速度 $ A^*(\tau)
瞬間ごみ生成速度 $ G^*(\tau)
ガベージコレクション処理速度 $ P
生きているデータとの比率
ミューテータ時間 $ \tau
無限に高速な理想的なコレクタ(あるいは、実用的にはガベージコレクションをしなくても十分なメモリがある場合)での時間軸での値
これを使って、区間 $ (\tau_1, \tau_2)における
メモリ割り付け量は、
$ \alpha^*(\tau_1, \tau_2) = \int^{\tau_2}_{\tau_1} A^*(\tau) d\tau
生成されるごみを
$ \gamma^*(\tau_1, \tau_2) = \int^{\tau_2}_{\tau_1} G^*(\tau)d\tau
と定義できる。
長さ$ \Delta \tauの区間で割り付けされるメモリの最大量は
$ \alpha^*(\Delta\tau) = \max_\tau \alpha^*(\tau, \tau + \Delta\tau)
となる。
これを使って最大割り付け速度を
$ a^*(\Delta\tau) = \frac{\alpha(\Delta\tau)}{\Delta\tau}
と本では定義されているが、これは脚注にもあるように、
$ a^* (ある区間の最大割り付け速度) と $ \alpha^* (ある区間の最大割り付け量)を注意深く区別せよ
とあって、気が狂ってるので、以下では最大割り付け速度を
$ allocSpeed^*(\Delta\tau)
と表記することにする……。
時刻 $ \tau の時点でのプログラムの必要メモリは、理想的には(断片化等を無視して)
$ m^*(\tau) = \alpha^*(0, \tau) - \gamma^*(0, \tau)
と書ける。
実時間をミューテータ時間に変換する関数
$ \Phi \colon t \to \tau
も必要である($ \tau \le t である)。
コレクタが動作している間はミューテータ時間が経過しないので、45度の傾きと、水平を持つ階段状になる？
ミューテータ時間の関数を$ f^*と書くのに対して、実時間の上での関数を $ fと書く。
つまり、時刻$ tにおけるプログラム中の生きているメモリは
$ m(t) = m^*(\Phi(t))
と書け、プログラム全体を通して必要になる最大メモリ量は
$ m = \max_t m(t) = \max_\tau m^*(\tau)
と書ける。
時間利用率
さらに2つのパラメータがある。
ミューテータのタイムスライス $ Q_T
コレクタのタイムスライス $ C_T
それぞれが1スライスでCPUを使える最大の時間
これらを使い、最小のミューテータ使用率を
$ u_T(\Delta t) = \frac{Q_T k + x}{\Delta t}
と表わせる。
分子の前者は完全なミューテータタイムスライスの合計
$ k は $ \Delta t の間のサイクル数
19.6の交互にコレクタとミューテータが実行されている時のことを意識して和で1サイクルとしている(最悪のケースの想定となっている(最小利用率だからそりゃそうか))。
$ k = \left\lfloor\frac{\Delta t}{Q_T+C_T}\right\rfloor
$ xは完了していないミューテータタイムスライスの合計
$ x = \max(0, (\Delta t - (Q_T + C_T) k) - C_T)
最小ミューテータ利用率について以下はなりたつ。
$ \lim_{\Delta t \to \infty} u_T(\Delta t) = \frac{Q_T}{Q_T + C_T}
$ Q_T が小さいほうが早く収束する。
$ \Delta t が小さいほど $ x がよく効いてくる。
コレクタは間欠的に動作するので$ u_T(\Delta t)は利用率の下限となる。
空間利用率
ミューテータの割付速度に大きく依存する。
コレクタの速度 $ P 一定と仮定すると、時刻 $ t において、$ m(t) の生きているデータを処理するのに $ \frac{m(t)}{P} のコレクタスレッドの時間が必要。
ミューテータの使う時間はその$ \frac{Q_T}{C_T} 倍である。
よって、時刻 $ t における空間オーバーヘッドは
$ e_T(t) = \alpha^*(\Phi(t), \Phi(t) + \frac{m(t)}{P} \frac{Q_T}{C_T} )
となる。
コレクタが動いている最中にも溜まってしまう割り付けの量のことを空間オーバーヘッドと呼んでいる
これを用いて、オーバーヘッドの最大値を
$ e_T = \max_t e_T(t)
と書ける。
オブジェクトを開放するまで、最悪3サイクルがMetronomeでは必要である。
1回が、最良ケース。
2回が、コレクションサイクルの開始後にごみとなったケース。
3回が、さらに回収前に移動させないといけないケース。 ← これなに？
これは移動型GCに共通する性質かもしれない
これを使うと、時刻 $ t において必要な理想的な空間は
$ s_T(t) \le m(t) + 3 e_T
と書けて、実行全体では
$ s_T \le m + 3 e_T
の空間が必要となる。
これは回収が全て最悪ケースで行なわれるという想定で、現実的には$ m + e_T あればよいと見込まれる。
現実的に、とは？
ミューテータによる変更
ライトバリアは全ての失なわれる/挿入される参照を保持するので、これも空間的コストを持つ。
ライトバリアによる空間的コストが有界であってほしい
nullの参照とマークがついたオブジェクトへの参照はそもそもライトバリアしないことにする
ライトバリアのコストを抑えつつ仕事量の上限をオブジェクトの最大数で抑えられる
これは間接的なメモリ割り付けとして計上される。 ← ？
$ \alpha^* の見積りでこれも考えとけよ ということか？
ライトバリアによる割り付け量の増加は定数倍で済むよ ということ？
鋭敏さ
パラメータの見積りが甘いと崩壊する。
以下のパラメータが出てきた。
割り付け速度 $ A^*(t) ← これ$ A(t) じゃない？
ごみ生成速度 $ G^*(t) 同様に $ G(t) ？
コレクタの処理速度 $ P
量子化パラメータ $ Q_T $ C_T
見ていくと
利用率$ u_T は$ Q_T 、$ C_T にのみ依存するので、安定。
余分に必要となる空間 $ e_T(t) は、アプリケーションの最大使用量 $ m と、区間で割り付ける量に依存。
$ m or$ allocSpeed^* を低く見積ると、$ s_T が発散(して割り付けに失敗)することがありうる。
$ Pも保守的に低く見積るのがよいだろう。
アプリケーションの稼働時間のほとんどを占める定常状態では、
割り付け速度が平均割り付け速度に近い
$ allocSpeed^* よりはるかにこれは小さい。
空間的オーバヘッド$ e_T(t) の分がコレクタによる回収量とバランスして、$ m(t)が$ mのほぼ定数倍で変化しなくなる
このとき、1回のコレクションサイクルは$ \Delta t = \frac{m(t)}{P} \frac{Q_T}{C_T} で表される
仕事ベーススケジューリングとの比較
仕事ベーススケジューリングでも同じような解析はできるかもだけど難しい。
時間ベースだと $ \Phi(t) は線形/fixedと思ってよいが、仕事ベースだと非線形/変動的/アプリケーション依存となる。
具体的に以下仕事ベースの解析をしているが、なんでここでやってるの……？ 章立て……。
パラメータ
仕事ベースミューテータ単位仕事量 $ Q_W
制御を手放すまでに割り付けていいメモリ量
仕事ベースコレクタ単位仕事量 $ C_W
手放すまでにしていい仕事量
仕事速度 $ P
コレクタの各タイムスライスでは、
$ d = \frac{C_W}{P}
の時間がかかる。
これが1回の停止時間
$ i 回の仕事単位でミューテータの動作する時間の合計の最小値$ \Delta\tau_i は
$ \alpha^*(\Delta\tau_i) = i Q_W
の $ \Delta\tau_i についての解の最小値。
$ \alpha^*(\Delta\tau) は、最大割り付け量なので、単調増加である。
よって $ \Delta\tau_i \gt \Delta\tau_{i-1} である。
よって反復法で解ける。
whileループを回せば解けることを反復法と呼んでいる
$ k を
$ kd +\Delta\tau_k \le \Delta t
を満たす最大の整数とする。($ k 回のサイクル)
$ \Delta\tau_k を$ k 回のミューテータの完全な仕事の合計、$ y を完了していない時間単位 $ y = \max(0, \Delta t - \Delta\tau_k - (k + 1) d) とする。
こうすると、区間$ \Delta tにおける最小ミューテータ利用率を
$ u_W(\Delta t) = \frac{\Delta\tau_k + y}{\Delta t}
と表わせる。
$ \Delta t \lt d の時、$ u_W(\Delta t) = 0 となってしまう。
1サイクルも仕事できなかったから、ずっとコレクタが仕事してた。
$ nQ_W バイトのような巨大な割り付けをすると、$ n 回のコレクタが動作して、$ nd の停止時間が生じ、この間のミューテータ利用率は0になる。
アプリ開発者は、リアルタイム制約を守るべくこれに留意する必要がある。
$ u_W(\Delta t) は、$ allocSpeed^*(\Delta\tau_i) 、$ P に依存している。
$ u_Wの式が依存するパラメータを見ればわかること
$ allocSpeed^* が速くなると$ \alpha^* が速くなるので、$ \Delta t_i が小さくなるということか？
リアルタイムの性能が要求される区間$ \Delta tが小さいアプリケーションについて考えると、
この区間中の割り付け速度が非常に高くなるはず(そういうアプリケーションが多そう)
結果、仕事ベースだと最小ミューテータ利用率のゆらぎが大きい
対照的に、時間ベースだとゆらぎは小さい
空間についての解析
時刻$ t での余分な領域は
$ e_W(t) = m(t) \frac{Q_W}{C_W}
実行全体では
$ e_W = m \frac{Q_W}{C_W}
となる。
$ m の見積りが正確な限り、これは正確になる。
$ Q_W \lt C_W でないと、$ e_W \lt m となる。
時刻$ t でのプログラム全体での必要なメモリは
$ s_W(t) \le m(t) + 3 e_W
実行全体では
$ s_W \le m + 3 e_W
となる。
移動型GCであればたいてい3サイクルの計算になりそう
比較まとめ
仕事ベースコレクタは、
$ mが精確に見積られている限り空間的な制限を満たす。
見積もりに失敗すると、ミューテータが自分の仕事をする時間がなくなる
最小ミューテータ利用率はリアルタイムの性能が要求される区間での割り付け速度に大きく依存する。
時間ベースコレクタでは、
最小ミューテータ利用率の保証は簡単。
必要とする空間は変動する。
見積もりに失敗すると、コレクタが仕事を完了できるだけの時間がなくなって、メモリ不足になる
頑健性
時間ベースだと、リアルタイムコレクションに必要な堅牢性がある。
パラメータの見積りが甘いと、十分な回収ができない。そういう時は割り付け速度を落として(または回収効率を上げて)しのぐしかない。
しかし、それでもデッドラインは守りたい。
回収効率を上げるには、世代別とすればよい。
他の方法として、ミューテータの実行速度を下げるという手もあるが、これに手を染めると、デッドラインミスにつながる。
デッドラインミスとは：リアルタイム制約を満たせなくなることか
余裕ベーススケジューリング(低優先度のミューテータを止める？)という手もある。十分な余裕があれば、デッドラインは守られる。
解決は次の章で！